On the Achievable Information Rates of Finite-State Input Two-Dimensional Channels with Memory

摘要

The achievable information rate of finite-state input two-dimensional (2-D)channels with memory is an open problem, which is relevant, e.g., forinter-symbol-interference (ISI) channels and cellular multiple-access channels.We propose a method for simulation-based computation of such information rates.We first draw a connection between the Shannon-theoretic information rate andthe statistical mechanics notion of free energy. Since the free energy of suchsystems is intractable, we approximate it using the cluster variation method,implemented via generalized belief propagation. The derived, fully tractable,algorithm is shown to provide a practically accurate estimate of theinformation rate. In our experimental study we calculate the information ratesof 2-D ISI channels and of hexagonal Wyner cellular networks with binaryinputs, for which formerly only bounds were known.